/FONT#1=BASL30/FONT#2=BASB30/FONT#3=NGR25/FONT#4=NGR20/FONT#5=NGB30/FONT#6=BASI30
␈↓↓␈↓α␈↓β␈↓∧␈↓¬␈↓ε␈↓α␈↓ ¬→STANFORD UNIVERSITY␈↓ ↓H
␈↓β␈↓ ¬_STANFORD, CALIFORNIA 94305␈↓ ↓H
␈↓∧COMPUTER SCIENCE DEPARTMENT␈↓ 
+   Telephone:␈↓ ↓H
␈↓ 
+415-497-4971␈↓ ↓H
␈↓↓␈↓ ε↓Aug 29, 1975␈↓ ↓H
␈↓ ↓H
␈↓ ↓H
␈↓ ↓H
␈↓ ↓H
␈↓ ↓H
␈↓ ↓H
␈↓ ↓H
␈↓ ↓H
␈↓ ↓H
Robert L. Ashenhurst, ACM Editor-in-Chief␈↓ ↓H
Institute for Computer Research␈↓ ↓H
The University of Chicago␈↓ ↓H
Chicago, Ill.  60637␈↓ ↓H
␈↓ ↓H
␈↓ ↓H
Dear Dr. Ashenhurst:␈↓ ↓H
␈↓ ↓H
␈↓ ↓HPerhaps␈αthis␈αletter␈αshould␈αbe␈αaddressed␈αto␈αthe␈αSIGCSE␈αinstead␈αof␈αto␈αthe␈αmembership␈αat␈αlarge,␈αbut␈αI␈↓ ↓H
␈↓ ↓Hfeel␈αthat␈αeducation␈αis␈αthe␈αbusiness␈αof␈αthe␈αwhole␈αcommunity.␈αThe␈αletter␈αaddresses␈αitself␈αparticularly␈αto␈↓ ↓H
␈↓ ↓Hthe␈α∞undergraduate␈α∞educational␈α∞policies.␈α∞The␈α∞general␈α
thesis␈α
of␈α
these␈α
remarks␈α
is␈α
that␈α
a␈α
fundamental␈↓ ↓H
␈↓ ↓Hrestructuring␈αof␈α␈↓εCurriculum␈α68␈↓↓␈α
is␈α
long␈α
overdue.␈α
In␈α
particular␈α
the␈α
beginning␈α
courses,␈α
which␈α
will␈α
make␈↓ ↓H
␈↓ ↓Hor␈αbreak␈αa␈αdepartment,␈αmust␈αreflect␈αa␈αmore␈αunified␈αlook␈αat␈αthe␈αfield␈αof␈αComputer␈αScience␈αgiving␈α
the␈↓ ↓H
␈↓ ↓Hnew␈α⊗student␈α⊗motivation␈α∃and␈α∃perspective.␈α∃Unless␈α∃a␈α∃beginning␈α∃student␈α∃can␈α∃be␈α∃convinced␈α∃that␈↓ ↓H
␈↓ ↓HComputer␈α
Science␈α
is␈α
something␈α
other␈α
than␈α
programming␈α
or␈α
hardware,␈α
then␈α
he␈α
becomes␈α
easy␈α
prey␈α
for␈↓ ↓H
␈↓ ↓Hother␈αdepartments.␈αAs␈αpresently␈αconstituted,␈αCurriculum␈α68␈αdoes␈αlittle␈αto␈αdispel␈αsuch␈αdoubts.␈αIt␈αis␈αmy␈↓ ↓H
␈↓ ↓Hbelief␈α⊂that␈α⊂much␈α⊂of␈α⊂the␈α∂fault␈α∂lies␈α∂in␈α∂the␈α∂data␈α∂structures␈α∂course,␈α∂I1.␈α∂Too␈α∂many␈α∂departments␈α∂have␈↓ ↓H
␈↓ ↓Hcopied␈α∞the␈α∞I1-Data␈α∞Structures␈α
description␈α
without␈α
proper␈α
regard␈α
for␈α
the␈α
importance␈α
of␈α
its␈α
place␈α
in␈↓ ↓H
␈↓ ↓Hthe␈α
68-graph.␈↓ ↓H
␈↓ ↓H
␈↓ ↓HIn␈α∂many␈α∂universities,␈α∂I1␈α∂is␈α∂the␈α∂first␈α∂␈↓εreal␈↓↓␈α∂computer␈α∂science␈α∂course.␈α∂The␈α∞previous␈α∞courses␈α∞are␈α∞more␈↓ ↓H
␈↓ ↓Happlications␈α⊂courses,␈α⊂covering␈α⊂basic␈α∂programming␈α∂and␈α∂perhaps␈α∂hardware␈α∂and␈α∂finite␈α∂mathematics.␈↓ ↓H
␈↓ ↓HThe␈αdifficulty␈αis␈α
that␈α
such␈α
a␈α
background␈α
does␈α
not␈α
adequately␈α
prepare␈α
a␈α
student␈α
for␈α
the␈α
usual␈α
dose␈α
of␈↓ ↓H
␈↓ ↓HI1.␈αAll␈αtoo␈αfrequently␈αthis␈αcourse␈αdeals␈αtoo␈αmuch␈αwith␈αtricks␈αand␈αtechniques␈αand␈αtoo␈αlittle␈αwith␈αideas␈↓ ↓H
␈↓ ↓Hand␈α
motivation.␈α
Other␈α
than␈α
a␈α
possible␈α
interest␈α
in␈α
toy␈α
problems␈α
or␈αa␈αdesire␈αto␈αplease␈αthe␈αinstructor,␈↓ ↓H
␈↓ ↓Hwhy␈α
should␈α
a␈α
student␈α
with␈α
such␈α
a␈α
meager␈α
background␈α
be␈α
interested␈α
in␈α
data␈α
structures?␈↓ ↓H
␈↓ ↓H
␈↓ ↓HOnce␈α⊂you␈α⊂start␈α⊂questioning␈α⊂the␈α⊂content␈α⊂of␈α∂I1,␈α∂other␈α∂doubts␈α∂arise.␈α∂Why␈α∂use␈α∂machine␈α∂language␈α∂to␈↓ ↓H
␈↓ ↓Hdescribe␈α∞data␈α∞structures?␈α∞We␈α∞don't␈α∞require␈α∞machine␈α∞language␈α∞for␈α∞courses␈α
on␈α
numerical␈α
analysis␈α
so␈↓ ↓H
␈↓ ↓Hwhy␈α∂not␈α∂treat␈α∂data␈α∂structures␈α∂with␈α∂the␈α∂same␈α∂respect?␈α∂It␈α∂is␈α∂therefore␈α∂desirable␈α∂to␈α∞use␈α∞a␈α∞high␈α∞level␈↓ ↓H
␈↓ ↓Hlanguage␈α
to␈α
describe␈α
data␈α
structure␈α
algorithms.␈↓ ↓H
␈↓ ↓H
␈↓ ↓HWe␈α∞should␈α∞also␈α∞think␈α∞about␈α∞the␈α∞courses␈α∞which␈α∞will␈α∞follow␈α∞I1␈α∞and␈α
what␈α
we␈α
can␈α
do␈α
to␈α
prepare␈α
the␈↓ ↓H
␈↓ ↓Hstudent␈α⊂for␈α⊂them.␈α⊂We␈α∂should,␈α∂if␈α∂possible,␈α∂prepare␈α∂students␈α∂for␈α∂courses␈α∂on␈α∂translator␈α∂construction,␈↓ ↓H
␈↓ ↓Hsystems␈α∀programming,␈α∀and␈α∀for␈α∀less␈α∀traditional␈α∪courses␈α∪on␈α∪correctness,␈α∪structured␈α∪programming,␈↓ ↓H
␈↓ ↓Hprogramming␈αmethodology.␈αI␈αbelieve␈αwe␈αmotivate␈αthese␈αlater␈αcourses␈α
by␈α
giving␈α
additional␈α
care␈α
to␈α
the␈↓ ↓H
␈↓ ↓Hpreparation␈α
of␈α
I1.␈↓ ↓H
␈↓ ↓H
␈↓ ↓H
␈↓ ↓H
␈↓ ↓HFirst␈α∩we␈α∩address␈α∩the␈α⊃problems␈α⊃of␈α⊃motivating␈α⊃the␈α⊃current␈α⊃content␈α⊃of␈α⊃I1.␈α⊃What␈α⊃was␈α⊃the␈α⊃␈↓εoriginal␈↓↓␈↓ ↓H
␈↓ ↓Hmotivation␈αfor␈αthese␈αtechniques␈αof␈αdata␈α
structuring?␈α
The␈α
tricks␈α
and␈α
techniques␈α
arose␈α
from␈α
real␈α
needs␈↓ ↓H
␈↓ ↓Hof␈α⊂programmers␈α⊂working␈α⊂on␈α⊂increasingly␈α⊂sophisticated␈α⊂projects.␈α⊂Though␈α⊂they␈α⊂arose␈α∂from␈α∂diverse␈↓ ↓H
␈↓ ↓Hproblem␈αareas,␈αmany␈αarose␈αin␈αthe␈αcontext␈αof␈αlanguage␈αimplementation;␈αand␈αthe␈α␈↓εideas␈↓↓␈αto␈α
be␈α
presented␈↓ ↓H
␈↓ ↓Hin␈α∪I1␈α∪can␈α∪all␈α∪be␈α∪handled␈α∪in␈α∪a␈α∪discussion␈α∪such␈α∪an␈α∩implementation.␈α∩Now␈α∩interjecting␈α∩language␈↓ ↓H
␈↓ ↓Himplementation␈α∂into␈α∂our␈α∂discussion␈α∞seems␈α∞like␈α∞a␈α∞step␈α∞backwards.␈α∞Before␈α∞anyone␈α∞should␈α∞undertake␈↓ ↓H
␈↓ ↓Hsuch␈α
a␈α
project␈α
he␈α
must␈α
have␈α
a␈α
clear␈α
understanding␈α
of␈α
all␈α
of␈α
the␈α
details␈α
of␈α
the␈α
language.␈↓ ↓H
␈↓ ↓H
␈↓ ↓HWhat␈αlanguage␈αshould␈αwe␈α
pick?␈α
Many␈α
exist␈α
and␈α
any,␈α
from␈α
machine␈α
language␈α
to␈α
high␈α
level␈α
language,␈↓ ↓H
␈↓ ↓Hcould␈αbe␈αused.␈αFor␈αa␈αcourse␈αin␈αthe␈αposition␈αof␈αI1␈αwe␈αalso␈αwant␈αa␈αlanguage␈αwhich␈αwe␈αcan␈αuse␈αto␈αtalk␈↓ ↓H
␈↓ ↓Habout␈αdata␈αstructures␈αat␈α
some␈α
level␈α
of␈α
abstraction.␈α
We␈α
are␈α
first␈α
interested␈α
in␈α
motivating␈α
the␈α
ideas,␈α
not␈↓ ↓H
␈↓ ↓Hin␈α∞bit-pushing␈α
and␈α
efficiency.␈α
So␈α
we␈α
would␈α
like␈α
a␈α
high␈α
level␈α
language␈α
suitable␈α
for␈α
describing␈α
data␈↓ ↓H
␈↓ ↓Hstructures␈α∀and␈α∀their␈α∪manipulations;␈α∪we␈α∪will␈α∪talk␈α∪about␈α∪the␈α∪techniques␈α∪of␈α∪I1␈α∪when␈α∪we␈α∪discuss␈↓ ↓H
␈↓ ↓Himplementation␈α∀of␈α∀the␈α∀language␈α∪and␈α∪need␈α∪to␈α∪understand␈α∪the␈α∪issues␈α∪of␈α∪representation␈α∪of␈α∪data␈↓ ↓H
␈↓ ↓Hstructures␈α
and␈α
the␈α
mechanization␈α
of␈α
data-structure␈α
algorithms.␈↓ ↓H
␈↓ ↓H
␈↓ ↓HWhat␈α
requirements␈α
should␈α
such␈αa␈αlanguage␈αhave?␈αIt's␈αsyntax␈αshould␈αbe␈αsimple␈αso␈αthat␈αthe␈αstudents␈↓ ↓H
␈↓ ↓Hcan␈αbecome␈αreasonably␈αproficient␈αin␈αa␈αvery␈αshort␈αtime.␈αIt␈αshould␈αhave␈αrecursion␈αfor␈αseveral␈αreasons:␈↓ ↓H
␈↓ ↓Hmany␈α⊃data␈α⊃structure␈α⊃problems␈α⊃are␈α⊃most␈α⊃easily␈α⊃described␈α⊃with␈α⊃this␈α⊃construct;␈α⊂the␈α⊂implementation␈↓ ↓H
␈↓ ↓Hmechanisms␈α⊗underlying␈α⊗recursion␈α⊗can␈α⊗be␈α⊗motivated␈α⊗easily␈α∃when␈α∃we␈α∃come␈α∃to␈α∃implementation␈↓ ↓H
␈↓ ↓Hquestions.␈↓ ↓H
␈↓ ↓H
␈↓ ↓HSince␈α∪we␈α∪are␈α∪teaching␈α∪programming␈α∪style,␈α∪we␈α∪must␈α∪have␈α∪the␈α∩ability␈α∩to␈α∩describe␈α∩abstract␈α∩data␈↓ ↓H
␈↓ ↓Hstructures␈α∞and␈α∞demonstrate␈α∞to␈α∞the␈α∞student␈α
the␈α
benefits␈α
of␈α
representation-independent␈α
programming␈↓ ↓H
␈↓ ↓Hand␈αstepwise-refinement;␈αbut␈αwe␈αmust␈αalso␈α
convince␈α
the␈α
student␈α
that␈α
these␈α
abstractions␈α
can␈α
indeed␈α
be␈↓ ↓H
␈↓ ↓Hturned␈α
into␈α
programs␈α
which␈α
run␈α
on␈α
a␈α
machine.␈↓ ↓H
␈↓ ↓H
␈↓ ↓HOne␈α∀on␈α∀the␈α∀most␈α∀troublesome␈α∀areas␈α∀for␈α∀students␈α∀is␈α∪in␈α∪developing␈α∪an␈α∪understanding␈α∪binding␈↓ ↓H
␈↓ ↓Hstrategies.␈αIndeed␈αone␈αof␈αthe␈αmost␈αdifficult␈αproblems␈αof␈αlanguage␈αdesign␈αis␈αthe␈αproper␈αunderstanding␈↓ ↓H
␈↓ ↓Hof␈α∃binding␈α∃and␈α∃environments.␈α∃We␈α∃should␈α∀take␈α∀care␈α∀to␈α∀discuss␈α∀the␈α∀implications␈α∀call-by-name,␈↓ ↓H
␈↓ ↓Hcall-by-value,␈α⊗and␈α⊗procedure-valued␈α⊗variables.␈α⊗After␈α∃a␈α∃proper␈α∃regard␈α∃for␈α∃their␈α∃complexity␈α∃is␈↓ ↓H
␈↓ ↓Hdeveloped␈α∂the␈α∂student␈α∂will␈α∂be␈α∞prepared␈α∞to␈α∞handle␈α∞the␈α∞data␈α∞structure␈α∞problems␈α∞which␈α∞arise␈α∞in␈α∞the␈↓ ↓H
␈↓ ↓Himplementations.␈↓ ↓H
␈↓ ↓H
␈↓ ↓HAs␈α∂we␈α∂are␈α∂describing␈α∂the␈α∂language␈α∂with␈α∂an␈α∞eye␈α∞both␈α∞towards␈α∞evaluation␈α∞and␈α∞implementation,␈α∞we␈↓ ↓H
␈↓ ↓Hshould␈α⊂be␈α⊂most␈α⊂careful␈α⊂in␈α⊂giving␈α⊂a␈α⊂precise␈α⊂description␈α⊂of␈α⊂the␈α⊂meaning␈α⊂of␈α⊂each␈α⊂construct␈α⊂of␈α⊂the␈↓ ↓H
␈↓ ↓Hlanguage.␈α∀Here␈α∀we␈α∀should␈α∀introduce␈α∀the␈α∀student␈α∀to␈α∀the␈α∀problems␈α∀of␈α∀semantics␈α∀and␈α∀language␈↓ ↓H
␈↓ ↓Hspecification.␈α
Since␈α
this␈α
is␈α
to␈α
be␈α
a␈αcourse␈αon␈αdata␈αstructures␈αa␈αnatural␈αspecification␈αof␈αour␈αlanguage␈↓ ↓H
␈↓ ↓Hmight␈αentail␈αan␈αoperational␈αor␈αinterpreter␈αdefinition.␈αThe␈αproject␈αentails␈αa␈αdescription␈αof␈αevaluation␈↓ ↓H
␈↓ ↓Hmechanism␈α∀as␈α∀a␈α∀program␈α∀in␈α∀our␈α∀language␈α∀and␈α∀a␈α∀description␈α∀of␈α∀language␈α∀constructs␈α∪as␈α∪data␈↓ ↓H
␈↓ ↓Hstructures.␈αThis␈αhas␈αat␈αleast␈αtwo␈αbenefits.␈αFirst,␈αit␈αshows␈αa␈αnon-trivial␈αapplication␈αof␈αdata␈αstructures.␈↓ ↓H
␈↓ ↓HSecond,␈α∂the␈α∂operational␈α∂description␈α∞is␈α∞a␈α∞high-level␈α∞implementation␈α∞of␈α∞our␈α∞language.␈α∞It␈α∞will␈α∞give␈α∞a␈↓ ↓H
␈↓ ↓Hconcise␈α
specification␈α
of␈α
even␈α
the␈αmost␈αtroublesome␈αconstructs.␈αThe␈αprecision␈αand␈αlevel␈αof␈αdetail␈αwill␈↓ ↓H
␈↓ ↓Hbe␈α
invaluable␈α
when␈α
we␈α
begin␈α
a␈α
discussion␈α
of␈α
the␈α
concrete␈α
implementation.␈↓ ↓H
␈↓ ↓H
␈↓ ↓H
␈↓ ↓H
␈↓ ↓HOnce␈α∪the␈α∪operational␈α∪description␈α∩is␈α∩digested␈α∩the␈α∩natural␈α∩question␈α∩is␈α∩implementation␈α∩on␈α∩a␈α∩␈↓εreal␈↓↓␈↓ ↓H
␈↓ ↓Hmachine.␈α⊗This␈α⊗discussion␈α⊗outlines␈α⊗the␈α∃static␈α∃orgainzation␈α∃of␈α∃a␈α∃machine,␈α∃giving␈α∃insights␈α∃and␈↓ ↓H
␈↓ ↓Hmotivation␈α
for␈α
problems␈α
of␈α
data␈α
structures,␈α
storage␈α
management,␈α
and␈α
symbol␈α
table␈α
orgainzation.␈↓ ↓H
␈↓ ↓H
␈↓ ↓HThe␈α⊃discussion␈α⊂of␈α⊂the␈α⊂run-time␈α⊂management␈α⊂of␈α⊂such␈α⊂a␈α⊂programming␈α⊂language␈α⊂will␈α⊂also␈α⊂involve␈↓ ↓H
␈↓ ↓Hcareful␈α
applications␈α
of␈α
data␈αstructuring.␈αA␈αnatural␈αway␈αto␈αapproach␈αthese␈αquestions␈αof␈αthe␈αdynamic␈↓ ↓H
␈↓ ↓Hstructure␈α⊂of␈α⊂the␈α⊂machine␈α⊂is␈α⊂to␈α⊂discuss␈α⊂compilers.␈α⊂Given␈α⊂a␈α⊂clear␈α⊂understanding␈α⊂of␈α⊂the␈α∂evaluation␈↓ ↓H
␈↓ ↓Hmechanism␈αand␈αan␈αunderstanding␈αof␈αthe␈αreal␈αmachine␈αwe␈α
can␈α
start␈α
asking␈α
what␈α
structure␈α
we␈α
need␈α
to␈↓ ↓H
␈↓ ↓Himpose␈α∂of␈α∂the␈α∂hardware␈α∂to␈α∂assure␈α∂proper␈α∂execution.␈α∂The␈α∂mechanisms␈α∂for␈α∂recursion,␈α∂and␈α∂binding␈↓ ↓H
␈↓ ↓Hstrategies␈α∩arise␈α∩here.␈α∩The␈α∩problems␈α∩binding␈α⊃strategies␈α⊃are␈α⊃easily␈α⊃discussed␈α⊃by␈α⊃this␈α⊃point␈α⊃in␈α⊃the␈↓ ↓H
␈↓ ↓Hdevelopment.␈↓ ↓H
␈↓ ↓H
␈↓ ↓HThe␈α∪questions␈α∩of␈α∩language␈α∩specification␈α∩lead␈α∩quite␈α∩naturally␈α∩to␈α∩more␈α∩theoretical␈α∩discussions␈α∩of␈↓ ↓H
␈↓ ↓Hsemantics␈α
of␈α
programming␈α
languages␈α
and␈α
correctness␈α
and␈α
equivalence␈α
of␈αprograms.␈αThe␈αbeginning␈↓ ↓H
␈↓ ↓Hstudent␈α∞must␈α∞be␈α∞made␈α∞aware␈α∞of␈α∞the␈α∞importance␈α
of␈α
correctness␈α
considerations␈α
and␈α
a␈α
course␈α
dealing␈↓ ↓H
␈↓ ↓Hwith␈α
abstract␈α
data␈α
structures,␈α
programming␈α
style␈α
and␈αlanguage␈αdescription␈αand␈αimplementation␈αis␈αa␈↓ ↓H
␈↓ ↓Hnatural␈α
setting␈α
for␈α
such␈α
a␈α
discussion.␈↓ ↓H
␈↓ ↓H
␈↓ ↓HThe␈αlanguage␈αwe␈αpick␈αfor␈αI1␈αshould␈αalso␈αbe␈α␈↓εreal␈↓↓.␈αThere␈αis␈αa␈αcertain␈αsoothing␈αeffect␈αon␈α
the␈α
student␈α
if␈↓ ↓H
␈↓ ↓Hhe␈α∪knows␈α∪that␈α∪he␈α∪is␈α∩not␈α∩the␈α∩subject␈α∩in␈α∩some␈α∩ill-conceived␈α∩language␈α∩design␈α∩experiment.␈α∩Many␈↓ ↓H
␈↓ ↓Hlanguages␈α∀still␈α∀meet␈α∀these␈α∀requirements.␈α∀LISP␈α∀is␈α∀one␈α∀which␈α∪has␈α∪a␈α∪rich␈α∪history␈α∪of␈α∪interesting␈↓ ↓H
␈↓ ↓Hprogramming␈αexamples.␈αWe␈αcan␈αcite␈αfifteen␈αyears␈αof␈αmost␈αinteresting␈αartificial␈αintelligence␈αprograms␈↓ ↓H
␈↓ ↓Hor␈α
clever␈α
compilers,␈α
or␈α
advanced␈α
interactive␈α
debuggers␈α
or␈α
editors,␈α
all␈α
written␈α
in␈α
LISP.␈↓ ↓H
␈↓ ↓H
␈↓ ↓HOnce␈αthe␈αideas␈αinvolved␈αin␈αdata␈αstructure␈αmanipulation␈αare␈αseen␈αin␈αa␈αrich␈αenvironment␈αlike␈αthat␈αof␈↓ ↓H
␈↓ ↓Hlanguage␈α
implementation,␈α
we␈α
can␈α
easily␈α
motivate␈α
questions␈α
about␈α
efficiency.␈α
Questions␈α
of␈α
storage␈α
and␈↓ ↓H
␈↓ ↓Hcontrol␈α
regimes␈αlead␈αnaturally␈αto␈αmore␈αcomplex␈αrepresentations␈αof␈αdata␈αstructures.␈αIt␈αis␈αat␈αthis␈αpoint␈↓ ↓H
␈↓ ↓Hthat␈α∞the␈α∞student␈α∞is␈α∞aware␈α
of␈α
the␈α
␈↓εreasons␈↓↓␈α
for␈α
studying␈α
data␈α
structures.␈α
Along␈α
the␈α
way␈α
we␈α
have␈α
also␈↓ ↓H
␈↓ ↓Hintroduced␈α∞them␈α∞to␈α∞abstraction␈α∞as␈α∞a␈α∞means␈α∞of␈α∞controlling␈α∞complexity,␈α∞recursion␈α∞as␈α∞a␈α
programming␈↓ ↓H
␈↓ ↓Htechnique,␈α⊃step-wise␈α⊃refinement␈α⊃as␈α⊃a␈α⊃programming␈α⊃style,␈α⊃operational␈α⊃definitions␈α⊂of␈α⊂programming␈↓ ↓H
␈↓ ↓Hlanguages,␈αand␈αthe␈αrelated␈αproblems␈αof␈α
translator␈α
construction.␈α
Not␈α
only␈α
does␈α
he␈α
understand␈α
the␈α
data␈↓ ↓H
␈↓ ↓Hstructuring␈α∂techniques,␈α∂but␈α∂he␈α∂understands␈α∂some␈α∂of␈α∂the␈α∂contexts␈α∂in␈α∂which␈α∂they␈α∂have␈α∞been␈α∞found␈↓ ↓H
␈↓ ↓Huseful.␈↓ ↓H
␈↓ ↓H
␈↓ ↓H
␈↓ ↓H
␈↓ ↓HPerhaps␈α
this␈α
seems␈α
like␈α
a␈α
lot␈α
for␈α
a␈α
beginning␈α
student.␈α
It␈α
has␈α
turned␈α
out␈α
not␈α
to␈α
be␈α
the␈α
case.␈↓ ↓H
␈↓ ↓H
␈↓ ↓HSo␈αwhere␈αare␈αwe?␈αI␈α
have␈α
claimed␈α
the␈α
most␈α
of␈α
the␈α
content␈α
of␈α
I1␈α
is␈α
very␈α
naturally␈α
motivated␈α
by␈α
courses␈↓ ↓H
␈↓ ↓Hwhich␈α∞come␈α∞␈↓εafter␈↓↓␈α∞I1.␈α∞I␈α∞have␈α∞claimed␈α∞that␈α∞we␈α∞need␈α∞a␈α
course␈α
to␈α
bridge␈α
the␈α
gap␈α
between␈α
computing␈↓ ↓H
␈↓ ↓Hcourses␈α⊂and␈α⊂computer␈α⊂science␈α⊂courses.␈α⊂Just␈α⊂what␈α⊂are␈α⊂we␈α⊂advocating?␈α⊂Our␈α∂initial␈α∂sortie␈α∂into␈α∂data␈↓ ↓H
␈↓ ↓Hstructures␈α∂has␈α∂turned␈α∂into␈α∂a␈α∂course␈α∂on␈α∂language␈α∂design␈α∂and␈α∞just␈α∞about␈α∞everything␈α∞else.␈α∞What␈α∞we␈↓ ↓H
␈↓ ↓Hclaim␈αthen,␈αis␈αthat␈αthe␈α68-graph␈αisn't␈αjust␈αout-of␈αdate,␈α
it's␈α
wrong.␈α
The␈α
presentation␈α
we␈α
are␈α
advocating␈↓ ↓H
␈↓ ↓Hisn't␈α
new;␈α
all␈α
but␈α
a␈α
few␈α
of␈α
the␈α
ideas␈α
are␈α
present␈α
in␈α
John␈α
McCarthy's␈α
early␈α
work␈α
on␈α
LISP␈α
and␈α
abstract␈↓ ↓H
␈↓ ↓Hsyntax;␈αall␈αthese␈αpapers␈αwere␈αavailable␈α
in␈α
1968.␈α
McCarthy␈α
is␈α
not␈α
even␈α
mentioned␈α
in␈α
the␈α
bibliography␈↓ ↓H
␈↓ ↓Hattached␈α
to␈α
I1!␈α
What␈α
is␈α
normally␈α
taught␈α
as␈α
a␈α
course␈α
on␈α
data␈α
structures,␈α
does␈α
not␈α
belong␈αat␈αa␈αpoint␈↓ ↓H
␈↓ ↓Hlike␈α∞I1␈α∞in␈α∞the␈α∞ACM␈α∞graph.␈α∞The␈α∞typical␈α∞student's␈α
background␈α
just␈α
is␈α
not␈α
sufficient␈α
to␈α
support␈α
this␈↓ ↓H
␈↓ ↓Happroach.␈αSuch␈αa␈αcourse␈αwould␈αhave␈αvalue␈αlater␈αin␈αthe␈αstudent's␈αcareer␈αwhen␈αproblems␈αof␈αefficiency␈↓ ↓H
␈↓ ↓Hhave␈α⊂relevance.␈α⊂But␈α⊂I1␈α⊂should␈α⊂be␈α⊂a␈α⊂feeder␈α⊂course␈α⊂for␈α∂courses␈α∂on␈α∂translator␈α∂construction,␈α∂systems␈↓ ↓H
␈↓ ↓Hprogramming,␈α
semantics␈α
of␈α
programming␈α
languages,␈α
and␈α
the␈α
rest␈α
of␈α
the␈α
courses␈αin␈αthe␈αdepartment.␈↓ ↓H
␈↓ ↓HThe␈α
computer␈α
science␈α
major␈α
must␈αget␈αa␈αrealistic␈αoverview␈αof␈αthe␈αfield␈αand␈αthe␈αinterested␈αbystander␈↓ ↓H
␈↓ ↓Hmust␈α
be␈α
tantalized␈α
into␈α
joining␈α
the␈α
ranks.␈↓ ↓H
␈↓ ↓H
␈↓ ↓HThere␈α∃have␈α∀been␈α∀several␈α∀attempts␈α∀at␈α∀revising␈α∀Curriculum␈α∀68␈α∀but␈α∀I␈α∀have␈α∀not␈α∀seen␈α∀a␈α∀major␈↓ ↓H
␈↓ ↓Hrestructuring␈α⊂proposed.␈α⊂An␈α⊂early␈α∂course␈α∂which␈α∂unifies␈α∂the␈α∂material␈α∂which␈α∂is␈α∂unique␈α∂to␈α∂computer␈↓ ↓H
␈↓ ↓Hscience,␈α⊃particularly␈α⊃the␈α⊃software␈α⊃areas,␈α⊃is␈α⊃needed␈α⊂badly.␈α⊂Hardware␈α⊂courses␈α⊂require␈α⊂a␈α⊂reasonable␈↓ ↓H
␈↓ ↓Hbackground␈α∩in␈α∩␈↓εreal␈↓↓␈α∩engineering␈α∩and␈α∩physics.␈α∩But␈α∩what␈α∩␈↓εreal␈↓↓␈α∩background␈α∩do␈α∩you␈α∩need␈α⊃to␈α⊃be␈α⊃a␈↓ ↓H
␈↓ ↓Hprogrammer?␈α
The␈α
usual␈α
answer␈α
is␈α
"none".␈α
And␈α
that's␈α
where␈α
the␈αproblems␈αstart.␈αMany␈αdepartments␈↓ ↓H
␈↓ ↓Hjustify␈α↔their␈α↔existence␈α↔by␈α↔offering␈α↔programming␈α↔classes,␈α↔supplying␈α⊗cannon␈α⊗fodder␈α⊗for␈α⊗other␈↓ ↓H
␈↓ ↓Hdepartments␈α∩and␈α∩for␈α∩industry.␈α∩Computing␈α∩classes␈α∩most␈α∩certainly␈α⊃should␈α⊃be␈α⊃taught␈α⊃by␈α⊃computer␈↓ ↓H
␈↓ ↓Hscientists,␈α∞but␈α∞the␈α∞departments␈α
must␈α
go␈α
beyond␈α
this␈α
image␈α
of␈α
a␈α
service␈α
bureau.␈α
They␈α
must␈α
become␈↓ ↓H
␈↓ ↓Hless␈α
sensitive␈α
to␈α
the␈α
immediate␈α
needs␈α
of␈α
industry␈α
and␈α
stop␈α
confusing␈α
dispensation␈α
of␈α
technical␈α
skill␈↓ ↓H
␈↓ ↓Hwith␈αeducation.␈αThe␈αdiscipline␈αis␈αnot␈αin␈αa␈αsufficiently␈αwell-defined␈α
stage␈α
that␈α
we␈α
can␈α
be␈α
dispensers␈α
of␈↓ ↓H
␈↓ ↓Hconventional␈αwisdom;␈αwe␈αshould␈αbe␈αadvocating␈αhow␈αthings␈α␈↓εshould␈αbe␈↓↓␈α
rather␈α
than␈α
pontificating␈α
about␈↓ ↓H
␈↓ ↓Hhow␈α
things␈α
␈↓εare␈↓↓.␈α
Dijkstra's␈α
␈↓εHumble␈α
Programmer␈↓↓␈α
should␈α
be␈α
required␈α
reading.␈↓ ↓H
␈↓ ↓H
␈↓ ↓HPerhaps␈αmy␈αapproach␈αsmacks␈αof␈αelitism;␈αI␈αclaim␈αnot␈αso.␈αI␈αclaim␈αthat␈αmany,␈αif␈αnot␈αall,␈αof␈αthe␈αcurrent␈↓ ↓H
␈↓ ↓Hdifficulties␈α∪hiding␈α∪under␈α∪the␈α∪blanket␈α∪of␈α∪␈↓εThe␈α∪Software␈α∩Problem␈↓↓␈α∩are␈α∩traceable␈α∩to␈α∩poorly␈α∩trained␈↓ ↓H
␈↓ ↓Hprogrammers.␈α
I␈α
claim␈α
that␈α
we␈αmust␈αexpect␈αprofessional␈αprogrammers␈αto␈αbe␈αas␈αsophisticated␈αas␈αtheir␈↓ ↓H
␈↓ ↓Hengineering␈α
or␈αmathematical␈αcounterparts.␈αIndeed,␈αmany␈αpeople␈αhave␈αnoted␈αthat␈αif␈αthe␈αpractitioners␈↓ ↓H
␈↓ ↓Hin␈αother␈αtechnical␈αfields␈αperformed␈α
in␈α
the␈α
cavalier␈α
manner␈α
of␈α
current␈α
programming␈α
methodology,␈α
the␈↓ ↓H
␈↓ ↓Hdeath␈α
toll␈α
would␈α
be␈α
enormous.␈α
The␈α
violence␈α
done␈α
by␈α
poor␈α
programming␈α
is␈α
not␈α
so␈αvisible␈αbut␈αis␈αat␈↓ ↓H
␈↓ ↓Hleast␈α∞as␈α∞severe.␈α∞The␈α∞problems␈α∞in␈α∞current␈α∞programming␈α∞practice␈α
are␈α
not␈α
those␈α
of␈α
efficiency␈α
but␈α
are␈↓ ↓H
␈↓ ↓Hthose␈α∂of␈α∂␈↓εcorrectness␈↓↓.␈α∂People␈α∂write␈α∂buggy␈α∂programs.␈α∂Faster␈α∞machines␈α∞will␈α∞not␈α∞solve␈α∞these␈α∞problems;␈↓ ↓H
␈↓ ↓Hfaster␈αmachines␈αor␈αautomatic␈αprogramming␈αsystems␈αwill␈αnot␈αovercome␈αpoorly␈αeducated␈αprogrammers.␈↓ ↓H
␈↓ ↓HI␈α⊂reiterate:␈α⊂these␈α⊂remarks␈α∂are␈α∂directed␈α∂toward␈α∂undergraduate␈α∂education;␈α∂graduate␈α∂students␈α∂should␈↓ ↓H
␈↓ ↓Hknow␈α∞how␈α∞to␈α∞take␈α∞care␈α∞of␈α∞themselves.␈α
Other␈α
technical␈α
departments␈α
expect␈α
their␈α
undergraduates␈α
to␈↓ ↓H
␈↓ ↓Hbecome␈αconversant␈αwith␈αthe␈αbasic␈αtools␈αof␈αthe␈αdiscipline.␈αThe␈αbasic␈αtools␈αof␈αcomputer␈αscience␈αare␈αnot␈↓ ↓H
␈↓ ↓Hprogramming␈αlanguages,␈α␈↓εper␈αse␈↓↓,␈αbut␈αare␈αthe␈αcultivation␈αof␈αmethods␈α
of␈α
thought.␈α
It␈α
has␈α
been␈α
remarked␈↓ ↓H
␈↓ ↓Hthat␈α
few␈α
programmers␈α
discover␈α
recursion;␈α
they␈α
are␈α
told␈α
about␈α
it.␈α
That's␈α
a␈α
shame.␈↓ ↓H
␈↓ ↓H
␈↓ ↓HThere␈α∀is␈α∀a␈α∀succinct␈α∀statement␈α∀by␈α∀C.␈α∀Strachey␈α∀which␈α∀reflects␈α∀my␈α∪attitude␈α∪about␈α∪programming␈↓ ↓H
␈↓ ↓Hlanguages␈α
and␈α
therefore␈α
my␈α
approach␈α
to␈α
data␈α
structures:␈↓ ↓H
␈↓ α_␈↓ε"I␈α∩always␈α∩worked␈α∩on␈α∩programming␈α∩languages␈α∩because␈α∩it␈α∩seems␈α∩to␈α∩me␈α∩that␈α∩until␈α⊃you␈α⊃could␈↓ ↓H
␈↓ ↓Hunderstand␈α∂those,␈α∂you␈α∂couldn't␈α∂understand␈α∂computers.␈α∞Understanding␈α∞them␈α∞doesn't␈α∞really␈α∞mean␈α∞only␈↓ ↓H
␈↓ ↓Hbeing␈α
able␈α
to␈α
use␈α
them.␈α
A␈α
lot␈α
of␈α
people␈α
can␈α
use␈α
them␈α
without␈α
understanding␈α
them."␈↓↓␈↓ ↓H
␈↓ εW
␈↓ εW
Yours sincerely,␈↓ εW
␈↓ εW
␈↓ εW
␈↓ εW
John R. Allen ␈↓ εW
Research Associate␈↓ εW
Computer Science Dept␈↓ εW
Artificial Intelligence Labs␈↓ εW
␈↓ εW
␈↓ ↓H
LISP is an excellent way to take intelligent but technically naive students rapidly␈↓ ↓H
to advanced topics in such a way that a coherent picture of much of␈↓ ↓H
modern computer science is presented.␈↓ ↓H
␈↓ ↓H